package com.salim.leetcode.$44;

import lombok.extern.slf4j.Slf4j;

@Slf4j
public class WildcardMatching {
    public boolean isMatch(String s, String p) {
        boolean[][] match=new boolean[s.length()+1][p.length()+1];
        match[s.length()][p.length()]=true;
        for(int i=p.length()-1;i>=0;i--){
            if(p.charAt(i)!='*')
                break;
            else
                match[s.length()][i]=true;
        }
        for(int i=s.length()-1;i>=0;i--){
            for(int j=p.length()-1;j>=0;j--){
                if(s.charAt(i)==p.charAt(j)||p.charAt(j)=='?')
                    match[i][j]=match[i+1][j+1];
                else if(p.charAt(j)=='*')
                    match[i][j]=match[i+1][j]||match[i][j+1];
                else
                    match[i][j]=false;
            }
        }
        return match[0][0];
    }

    public static void main(String[] args) {
        WildcardMatching w = new WildcardMatching();
        log.info("WildcardMatching输出结果1：{}", w.isMatch("aa","a"));
        log.info("WildcardMatching输出结果2：{}", w.isMatch("aa","a*"));
        log.info("WildcardMatching输出结果3：{}", w.isMatch("cb","?a"));
        log.info("WildcardMatching输出结果4：{}", w.isMatch("adceb","*a*b"));
        log.info("WildcardMatching输出结果5：{}", w.isMatch("acdcb","a*c?b"));
        log.info("WildcardMatching输出结果6：{}",w.isMatch("abefcdgiescdfimde","ab*cd?i*de"));
        log.info("WildcardMatching输出结果7：{}",w.isMatch("leetcode","*e*t?d*"));
        log.info("WildcardMatching输出结果8：{}",w.isMatch("aaaa","***a"));
        log.info("WildcardMatching输出结果9：{}",w.isMatch("c","*?*"));
        log.info("WildcardMatching输出结果10：{}",w.isMatch("abbaabbbbababaababababbabbbaaaabbbbaaabbbabaabbbbbabbbbabbabbaaabaaaabbbbbbaaabbabbbbababbbaaabbabbabb","***b**a*a*b***b*a*b*bbb**baa*bba**b**bb***b*a*aab*a**"));

//        log.info("FirstMissingPositive输出结果3：{}", t.trap(new int[]{3,4,-1,1}));
//        log.info("FirstMissingPositive输出结果4：{}", t.trap(new int[]{7,8,9,11,12}));
    }
}
